/** 
  *https://leetcode.cn/problems/count-complete-tree-nodes/submissions/564733326/
 * 222. 完全二叉树的节点个数
 * medium,  2024.9.14
 * 二分搜索
*/
//参考老师上课代码

class Solution {
public:
    int countNodes(TreeNode* root) {
        if(root==nullptr)return 0;
        int ll =1,rr=50001;
        while(ll<rr){
            int m = (ll + rr + 1 )>> 1;
            if (check(root,m)!=nullptr)
                ll=m;
            else 
                rr=m-1;

        }
        return l;
    }
    TreeNode* check(TreeNode *root,int k){
        if (nullptr==root)
            return nullptr;
        if(k==1)
            return root;
        TreeNode *parent = check(root,k/2);
        if (parent==nullptr)
            return nullptr;
        if(k==k/2*2)
            return parent->left;
        else
            return parent->right;
    }
};